Linear equations occur frequently in all branches of science and engineering, and effective methods are needed for solving them. Furthermore, many science and engineering problems lead not to a single equation, but to a system of equations. The object of solving the system is to find values of all unknowns that satisfy all equations simultaneously.
The values of the solution set of a system of linear equations depend on the coefficients, a.sub.ij, of the system. The rectangular array of these coefficients in their m rows and n columns is called an m.times.n matrix A. Various methods for solving systems of linear equations use various operations on matrices, such as addition of or multiplication by a scalar, a vector, or another matrix. These methods have varying degrees of complexity, and the simpler methods are often limited to special cases or well conditioned matrices.
Another calculation involving matrices is matrix inversion. The conventional method of matrix inversion treats the matrix as a system of linear equations, but has a solution complexity of O(n.sup.3).
In performing calculations with matrices, especially when working with a large number of coefficients, it is desirable to use a computer to take the place of human calculations. Criteria for solution methods include processing speed and the number of processors required by a desired solution.
Processing speed is related to the ability to "parallelize" a calculation. Parallelization means that multiple operations may be performed simultaneously, thereby reducing the time required to obtain the desired result. Yet, many existing parallel methods involving matrix calculations are limited to well conditioned matrices. Another problem with existing methods is a susceptibility to round off errors.
Furthermore, existing parallel processing methods have sizable hardware demands. Thus, although some methods have reduced calculation complexity to 0(n) and 0(n.sup.2), they require a large number of processors. Other methods permit the calculation to be decomposed for a fixed number of processors, but invite decomposition penalties.
Thus, there is a need for a parallel processing system that speeds up calculations involving matrices. The processing system should accommodate general cases and permit the use of robust algorithms. For calculations with large matrices, the processing system should also not demand a large number of processors and permit decomposition without penalties. Finally, the system should maximize the speedup obtainable for a given number of processors.